package com.gwcloud.leetcode.tags.greed;

import java.util.Arrays;
import java.util.Comparator;

/** 
* @ClassName   : Leetcode0452 
* @author      : ganwei 
* @date        : 2020年5月17日 
* @Description : 452 用最少数量的箭引爆气球 
*/
public class Leetcode0452 {
	/**
	 * -解题思路，贪心第二例，该题与区间调度一致，即找出最多的不重叠区域
	 */
    public int findMinArrowShots(int[][] points) {
		if( points.length == 0) return 0;
	    Arrays.sort(points, new Comparator<int[]>() {
	        public int compare(int[] a, int[] b) {
	            return a[1] - b[1];
	        }
	    });
	    
	    int count = 1;
	    int x_end = points[0][1];
	    for(int[] point : points) {
	    	int start = point[0];
	    	if(start > x_end) {
	    		count++;
	    		x_end = point[1];
	    	}
	    }
	    
    	return count;
    }
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	
    }
}
